Graf pla

Exemples de grafs
Planar	No planar

En teoria de grafs, un graf pla o planar és un graf que pot ser dibuixat en un pla sense que les arestes s'intersequin (o utilitzant una definició més formal, que aquest graf pugui ser "embegut" en un pla).^[1][2] Un graf no és pla si no pot ser dibuixat sobre un pla sense que les seves arestes s'intersequin. Hi ha dos grafs no plans minimals; K₅ i K_3,3. Tots els grafs no plans contenen almenys un d'aquests subgrafs minimals.

En canvi, el graf complet K₄ és pla, perquè pot ser redibuixat sense que les arestes es creuin, passant una de les diagonals per l'exterior.

Per poder comprovar la planaritat d'un graf, primer s'ha d'adequar a una sèrie de criteris bàsics:

• El graf és connex. Si tenim un graf inconnex, podem considerar cada part com a graf connex independent.
• No té cap vèrtex de grau 1. Si conté vèrtexs de grau 1, per tant amb una sola aresta, aquests es poden eliminar de l'estructura sense risc a modificar-ne la planaritat.